package com.jhy.suixianglu.daima20221213;

import com.jhy.suixianglu.daima20221212.ListNode;

/**
 * 反转链表
 */
public class ReverseLinkedList {
    /**
     * 双指针的做法
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        // 定义一个前驱节点 指向null
        ListNode pre = null;
        // 定义一个当前节点
        ListNode cur = head;
        // 定义一个临时节点
        ListNode temp = null;
        // 1、终止条件
        while (cur != null) {
            // 先保存临时节点
            /**
             * 之所以在这里保存临时节点
             * 是因为这个连接是反转之前的。
             * 现在我们将这个线断开了。
             * 所以怕找不到这个原先的节点
             * 所以先保存到。
             */
            temp = cur.next;
            // 先赋值cur的下一个节点
            cur.next = pre;
            /**
             * 整体移动
             */
            // 先移动pre
            pre = cur;
            // 后移动cur
            cur = temp;
        }
        // 返回新链表的头节点
        return pre;
    }

    /**
     * 递归做法
     * @param head
     * @return
     */
     public  ListNode reverseList2(ListNode head){
       return  reverse(head,null);
     }

    private ListNode reverse(ListNode cur,ListNode pre) {
         // base case 如果当前为空 我们就放回pre
         if(cur == null){
             return pre;
         }
         // 保存当前临时的节点
         ListNode temp = cur.next;
         cur.next = pre;
         return  reverse(temp,cur);
    }
}
